1. Field of the Invention The present invention is related to improved fast-Fourier-transform (FFT) analyzers. It is directed to both the butterfly circuits and the interconnection of the butterfly circuits to form FFT analyzers.
2. Description of the Prior Art
The use of the discrete Fourier transform (DFT) for the frequency-domain analysis and design of signals and systems came into widespread use after the publication of the paper "An Algorithm for the Machine Calculation of Complex Fourier Series, in" Math. Computation., vol. 19, April 1965, pp. 297-301 by Cooley, J. W. and Tukey, J. W. describing, in general, the decomposition of an N-point DFT into a number of DFTs of a smaller size and, in particular, the radix-2 decimation-in-time (DIT) algorithm. The radix-2 decimation-infrequency (DIF) algorithm was reported later by Gentleman, W. M. and Sande, G. in "Fast Fourier Transforms-for Fun and Profit," in Proc. AFIPS, Joint Computer Conf., vol. 29, 1966, pp. 563-578. However, both the DIT and DIF algorithms, in general, are referred to as Cooley-Tukey algorithms. A detailed description and the history of the development of these algorithms can be found in Special Issue on FFT and Applications, IEEE Trans. Audio Electroacoust., vol. AU-15, June 1967. Despite the subsequent development of other algorithms, it is the Cooley-Tukey radix-2 algorithm that has been most widely used as presented originally without any significant changes, due to the simplicity, regularity, and efficiency of the resulting computational structure. A drawback of the computational structure of the Cooley-Tukey radix-2 algorithm is that it requires more complex multiplications compared with that of the higher-radix algorithms. In addition, this structure has the overheads of bit-reversal and data-swapping operations. This disclosure reports the invention of a large set of computational structures, designated as plus-minus (PM) structures, derived from a new family of radix-2 algorithms, designated as the plus-minus (PM) algorithms.